package com.love.dynamic;

/**
 * 99.最小路径和
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：一个机器人每次只能向下或者向右移动一步。

 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 输出：7
 解释：因为路径 1→3→1→1→1 的总和最小。
 示例 2：

 输入：grid = [[1,2,3],[4,5,6]]
 输出：12

 */
public class MinPathTotal {


    public static void main(String[] args) {
        int[][] grid = {
                {1,3,1},
                {1,5,1},
                {4,2,1}
        };
        System.out.println(minPathSum1(grid));
    }


    public static int minPathSum1(int[][] grid){
        return f1(grid,grid.length -1,grid[0].length-1);
    }

    /**
     * 从(0,0)到(i,j)最小路径和
     * 一定每次只能向右或者向下
     * @param grid
     * @param i
     * @param j
     * @return
     */
    public static int f1(int[][] grid,int i,int j){
        if( i == 0 && j == 0){
            return grid[0][0];
        }
        int up = Integer.MAX_VALUE;
        int left = Integer.MAX_VALUE;
        // 不是在第 0 行，就可以从上向下移动一步
        if(i > 0){
          up = f1(grid,i-1,j);
        }
        // 不是在第 0 列，就可以从左向右移动一步
        if(j > 0){
            left = f1(grid,i,j - 1);
        }
        return grid[i][j] + Math.min(up,left);
    }

    /**
     * 记忆化搜索的动态规划
     * @param grid
     * @return
     */
    public static int minPathSum2(int[][] grid){
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = -1;
            }
        }
        return f1(grid,m-1,n-1,dp);

    }

    public static int f1(int[][] grid,int i,int j,int[][] dp){
        if( i == 0 && j == 0){
            return grid[0][0];
        }
        if(dp[i][j] != -1){
            return dp[i][j];
        }
        int up = Integer.MAX_VALUE;
        int left = Integer.MAX_VALUE;
        // 不是在第 0 行，就可以从上向下移动一步
        if(i > 0){
            up = f1(grid,i-1,j,dp);
        }
        // 不是在第 0 列，就可以从左向右移动一步
        if(j > 0){
            left = f1(grid,i,j - 1,dp);
        }
        dp[i][j] = grid[i][j] + Math.min(up,left);
        return dp[i][j];
    }


    /**
     * 严格位置推断
     * @param grid
     * @return
     */
    public static int minPathSum3(int[][] grid){
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] += grid[i][0] + dp[i-1][0];
        }

        for (int i = 1; i < n; i++) {
            dp[0][i] += grid[0][i] + dp[0][i-1];
        }

        for (int i = 1;i < m; i++){
            for (int j = 1;j < n; j++){
                dp[i][j] = grid[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];

    }

    /**
     * 严格位置依赖 + 空间压缩
     * @param grid
     * @return
     */
    public static int minPathSum4(int[][] grid){
         int n = grid.length;
         int m = grid[0].length;
         // 先让dp表，变成想象中的表的第0行的数据
         int[] dp = new int[m];
         dp[0] = grid[0][0];
        for (int j = 1; j < m; j++) {
            // i = 1,dp表变成想象中的表的第1行的数据
            // i = 2,dp表变成想象中的表的第1行的数据
            // i = 3,dp表变成想象中的表的第1行的数据
            // ...
            // i = n - 1,dp表变成想象中的表的第n-1行的数据
            dp[j] = dp[j - 1] + grid[0][j];
        }
        for (int i = 0; i < n; i++) {
            dp[0] += grid[i][0];
            for (int j = 0; j < m; j++) {
                dp[j] = Math.min(dp[j - 1],dp[j] + grid[i][j] );
            }
        }
        return dp[m - 1];
    }



}
